package com.shm.leetcode;
/**
 * 208. 实现 Trie (前缀树)
 * 实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
 *
 * 示例:
 *
 * Trie trie = new Trie();
 *
 * trie.insert("apple");
 * trie.search("apple");   // 返回 true
 * trie.search("app");     // 返回 false
 * trie.startsWith("app"); // 返回 true
 * trie.insert("app");
 * trie.search("app");     // 返回 true
 * 说明:
 *
 * 你可以假设所有的输入都是由小写字母 a-z 构成的。
 * 保证所有输入均为非空字符串。
 */

import java.util.HashMap;
class TrieNode{
    //关键要定义好TrieNode类

    //定义某一节点的值
    char c;
    //建立哈希键-值对
    HashMap<Character,TrieNode> children = new HashMap<>();
    //判断是否完整单词
    boolean isWord;
    TrieNode(){

    }
    TrieNode(char c){
        this.c = c;
    }

}
class Trie {
    //定义根节点
    TrieNode root;

    /** Initialize your data structure here. */
    public Trie() {
        //实现根节点
        root = new TrieNode();
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        //把根节点的子节点全部存入哈希表
        HashMap<Character, TrieNode> child = root.children;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            TrieNode trieNode;
            //把根节点的子节点全部存入哈希表
            if(child.containsKey(c)){
                trieNode = child.get(c);
            }else {
                //若根节点不含此字符，则插入字符并生成新节点
                trieNode = new TrieNode(c);
                child.put(c,trieNode);
            }
            //更新哈希表为此节点的所有子节点
            child = trieNode.children;
            //若到达字符串最后一个字则判断为true
            if(i==word.length()-1){
                trieNode.isWord=true;
            }
        }
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode trieNode = searchNode(word);
        return trieNode != null && trieNode.isWord;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TrieNode trieNode = searchNode(prefix);
        return trieNode != null;
    }

    public TrieNode searchNode(String str) {
        HashMap<Character, TrieNode> child = root.children;
        //先让指针节点置null
        TrieNode trieNode = null;

        //跟插入很像
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (child.containsKey(c)){
                trieNode = child.get(c);
                child = trieNode.children;
            }else {
                return null;
            }
        }
        //最终返回字符串的最后一个字符所在的节点
        return trieNode;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

/**
 * 方法一：字典树
 * \text{Trie}Trie，又称前缀树或字典树，是一棵有根树，其每个节点包含以下字段：
 *
 * 指向子节点的指针数组 \textit{children}children。对于本题而言，数组长度为 2626，即小写英文字母的数量。此时 \textit{children}[0]children[0] 对应小写字母 aa，\textit{children}[1]children[1] 对应小写字母 bb，…，\textit{children}[25]children[25] 对应小写字母 zz。
 * 布尔字段 \textit{isEnd}isEnd，表示该节点是否为字符串的结尾。
 * 插入字符串
 *
 * 我们从字典树的根开始，插入字符串。对于当前字符对应的子节点，有两种情况：
 *
 * 子节点存在。沿着指针移动到子节点，继续处理下一个字符。
 * 子节点不存在。创建一个新的子节点，记录在 \textit{children}children 数组的对应位置上，然后沿着指针移动到子节点，继续搜索下一个字符。
 * 重复以上步骤，直到处理字符串的最后一个字符，然后将当前节点标记为字符串的结尾。
 *
 * 查找前缀
 *
 * 我们从字典树的根开始，查找前缀。对于当前字符对应的子节点，有两种情况：
 *
 * 子节点存在。沿着指针移动到子节点，继续搜索下一个字符。
 * 子节点不存在。说明字典树中不包含该前缀，返回空指针。
 * 重复以上步骤，直到返回空指针或搜索完前缀的最后一个字符。
 *
 * 若搜索到了前缀的末尾，就说明字典树中存在该前缀。此外，若前缀末尾对应节点的 \textit{isEnd}isEnd 为真，则说明字典树中存在该字符串。
 *
 * 复杂度分析
 *
 * 时间复杂度：初始化为 O(1)O(1)，其余操作为 O(|S|)O(∣S∣)，其中 |S|∣S∣ 是每次插入或查询的字符串的长度。
 *
 * 空间复杂度：O(|T|\cdot\Sigma)O(∣T∣⋅Σ)，其中 |T|∣T∣ 为所有插入字符串的长度之和，\SigmaΣ 为字符集的大小，本题 \Sigma=26Σ=26。
 *
 * 作者：LeetCode-Solution
 * 链接：https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/shi-xian-trie-qian-zhui-shu-by-leetcode-ti500/
 */
class Triee {
    private Triee[] children;
    private boolean isEnd;

    public Triee() {
        children = new Triee[26];
        isEnd = false;
    }

    public void insert(String word) {
        Triee node = this;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                node.children[index] = new Triee();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        Triee node = searchPrefix(word);
        return node != null && node.isEnd;
    }

    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    private Triee searchPrefix(String prefix) {
        Triee node = this;
        for (int i = 0; i < prefix.length(); i++) {
            char ch = prefix.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                return null;
            }
            node = node.children[index];
        }
        return node;
    }
}